package study.datastructure.heap;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-11-03 20:12
 */

/**
 2024/11/3,
 */

import com.sun.xml.internal.ws.runtime.config.TubelineFeatureReader;
import study.datastructure.queue.impl.MaxHeapPriorityQueue;

import java.util.Arrays;

/**
 * 大顶堆
 */

public class MaxHeap {

    private int size;
    private int [] array;

    public MaxHeap(int [] array){
        this.array=array;
        this.size=array.length;
        heapify();
    }
    public void heapify(){
        for(int i=size/2-1;i>=0;i--){
            down(i);
        }
    }

    /**
     * 增加元素
     * @param inserted
     * @return 是否成功
     */
    public boolean offer(int inserted){
        if (size==array.length){
            return false;
        }
        //添加到数组尾部
        array[size++]=inserted;

        //添加元素 上浮到顶
        up(size-1);
        return true;
    }

    /**
     * 获取最大值
     * @return
     */
    public int getMax(){
        return array[0];
    }

    /**
     * 替换堆顶元素
     * @param value
     */
    public void replace(int value){
        array[0]=value;
        down(0);
    }

    /**
     * 修改元素
     * @param index
     * @param value
     */
    public void update(int index,int value){
        array[index]=value;
        if (array[index]>array[(index-1)/2]){
            up(index);
        }else {
            down(index);
        }
    }



    /**
     * 取出堆顶元素
     * @return
     */
    public int poll(){
        int max=array[0];
        //移除堆顶元素
        array[0]=array[--size];
        down(0);
        return max;
    }


    private void up(int index){
        //找到父节点
        int parent=(index-1)/2;

        //交换值
        if(parent>=0&&array[parent]<array[index]){
            swap(parent,index);
            up(parent);
        }
    }



    /**
     * 下潜  跟所有 相关的孩子 交换 往下潜
     * @param i
     */
    private void down(int i){
        int left=2*i+1;
        int right=left+1;

        int max=i;

        if (left<size&&array[left]>array[max]){
            max=left;
        }
        if (right <size&&array[right]>array[max]){
            max=right;
        }
        if(max!=i){
            swap(i,max);
            down(max);
        }
    }

    private void swap(int i,int j){
        int t=array[i];
        array[i]=array[j];
        array[j]=t;
    }

    @Override
    public String toString() {
        return "MaxHeap{" +
                "array=" + Arrays.toString(array) +
                '}';
    }



    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(new int[]{ 1, 2, 3, 5});
        System.out.println("Initial MaxHeap: " + maxHeap);

        System.out.println(maxHeap.offer(10)?"success to Offered 10":"Heap is full");
        System.out.println("After inserting 10: " + maxHeap);

        System.out.println("Current Max: " + maxHeap.getMax());

        int removedMax = maxHeap.poll();
        System.out.println("Removed Max: " + removedMax);
        System.out.println("MaxHeap after polling: " + maxHeap);

        maxHeap.replace(15);
        System.out.println("After replacing top with 15: " + maxHeap);

        maxHeap.update(2, 8);
        System.out.println("After updating index 2 to 8: " + maxHeap);

        MaxHeap heap =new MaxHeap(new int[]{ 5, 3,2,4, 1});
        //堆排序
        while (heap.size>1){
            //- 将堆顶的最大值与堆的最后一个元素交换。这将最大值放在数组的末尾。
            //- 然后，减少堆的大小（不再考虑已排序的部分）。
            heap.swap(0,heap.size-1);
            heap.size--;
            heap.down(0);
        }


        System.out.println("After mergeSort: " + heap);
    }
}
